#include"AvlTree.h"

template<typename T>
AvlTree<T>::AvlTree()
{
	head = head->BuyNode(0);
}

template<typename T>
AvlTree<T>::~AvlTree()
{
	AvlNode<T>* p = head->left;
	while (p != nullptr)
	{
		Delete(p->key);
		p = head->left;
	}
	head->FreeNode(head);
}

template<typename T>
void AvlTree<T>::InOrder()
{
	if (IsEmpty()) return;
	_InOrder(head->parent);
	std::cout << std::endl;
}

template<typename T>
void AvlTree<T>::NoRecInOrder()
{
	AvlNode<T>* p = head->left;
	while (p != nullptr)
	{
		std::cout << p->key << " ";
		p = NextNode(p);
	}
	std::cout << std::endl;
}
template<typename T>
void AvlTree<T>::MirrorNoRecInOrder()
{
	AvlNode<T>* p = head->right;
	while (p != nullptr)
	{
		std::cout << p->key << " ";
		p = PreNode(p);
	}
	std::cout << std::endl;
}

template<typename T>
bool AvlTree<T>::Insert(const T& key)
{
	if (nullptr == head->parent)
	{
		head->parent = head->BuyNode(key);
		assert(head->parent != nullptr);
		head->left = head->parent;
		head->right = head->parent;
		head->parent->parent = head;
	}
	else
	{
		AvlNode<T>* p = head->parent;
		AvlNode<T>* pa = p->parent;
		while (p != nullptr && p->key != key)
		{
			pa = p;
			p = p->key < key ? p->right : p->left;
		}
		if (p != nullptr && p->key == key) return false;
		p = p->BuyNode(key);
		assert(p != nullptr);
		p->parent = pa;
		key > pa->key ? pa->right = p : pa->left = p;
		if (head->left->key > key)
		{
			head->left = p;
		}
		if (head->right->key < key)
		{
			head->right = p;
		}
		AdjustTree(p);
	}
	++cursize;
	return true;
}

template<typename T>
bool AvlTree<T>::Delete(const T& key)
{
	if (IsEmpty()) return false;
	AvlNode<T>* p = NoRecFindValue(key);
	if (nullptr == p) return false;

	if (p == head->left) head->left = NextNode(p);
	if (p == head->right) head->right = PreNode(p);

	if (p->left != nullptr && p->right != nullptr)
	{
		AvlNode<T>* pnext = NextNode(p);
		p->key = pnext->key;
		p = pnext;
	}
	AvlNode<T>* pa = p->parent;
	AvlNode<T>* child = p->left != nullptr ? p->left : p->right;
	if (child != nullptr) child->parent = pa;
	if (pa == head) head->parent = child;
	else
	{
		if (pa->left == p) pa->left = child;
		else pa->right = child;
	}
	p->FreeNode(p);
	cursize--;
	return true;
}

template<typename T>
AvlNode<T>* AvlTree<T>::FindValue(const T& key)
{
	if (IsEmpty()) return nullptr;
	return _FindValue(head->parent, key);
}

template<typename T>
AvlNode<T>* AvlTree<T>::NoRecFindValue(const T& key)
{
	if (IsEmpty()) return nullptr;
	AvlNode<T>* p = head->parent;
	while (p != nullptr && key != p->key)
	{
		p = key > p->key ? p->right : p->left;
	}
	return p;
}

template<typename T>
int AvlTree<T>::GetSize()
{
	return cursize;
}

template<typename T>
AvlNode<T>* AvlTree<T>::GetHead()
{
	return head;
}

template<typename T>
bool AvlTree<T>::IsEmpty()
{
	return nullptr == head->parent;
}

template<typename T>
bool AvlTree<T>::Is_BSTTree(AvlNode<T>* root)
{
	if (nullptr == root) return true;
	AvlNode<T>* pre = head->left;
	AvlNode<T>* p = NextNode(pre);
	while (p != nullptr)
	{
		if (pre->key > p->key) return false;
		pre = p;
		p = NextNode(p);
	}
	return true;
}

template<typename T>
bool AvlTree<T>::Is_AVLTree(AvlNode<T>* root)
{
	return DepthOfBinaryTree(root) != -1;
}

template<typename T>
void AvlTree<T>::_InOrder(AvlNode<T>* root)
{
	if (nullptr == root) return;
	else
	{
		_InOrder(root->left);
		std::cout << root->key << " ";
		_InOrder(root->right);
	}
}

template<typename T>
AvlNode<T>* AvlTree<T>::_FindValue(AvlNode<T>* root, const T& key)
{
	if (nullptr == root || key == root->key) return root;
	else if (key < root->key) return  _FindValue(root->left, key);
	else return _FindValue(root->right, key);
}

template<typename T>
AvlNode<T>* AvlTree<T>::NextNode(AvlNode<T>* node)
{
	if (nullptr == node) return nullptr;
	if (node->right != nullptr)
	{
		node = node->right;
		while (node->left != nullptr)
		{
			node = node->left;
		}
		return node;
	}
	while (node->parent != head)
	{
		AvlNode<T>* pa = node->parent;
		if (pa->left == node) return pa;
		node = pa;
	}
	return nullptr;
}

template<typename T>
AvlNode<T>* AvlTree<T>::PreNode(AvlNode<T>* node)
{
	if (nullptr == node) return nullptr;
	if (node->left != nullptr)
	{
		node = node->left;
		while (node->right != nullptr) node = node->right;
		return node;
	}
	while (node->parent != head)
	{
		AvlNode<T>* pa = node->parent;
		if (pa->right == node) return pa;
		node = pa;
	}
	return nullptr;
}

template<typename T>
void AvlTree<T>::RotateLeft(AvlNode<T>* node)
{
	AvlNode<T>* pa = node->parent;
	AvlNode<T>* pNewRoot = node->right;

	node->right = pNewRoot->left;
	if (pNewRoot->left != nullptr)
	{
		pNewRoot->left->parent = node;
	}

	pNewRoot->left = node;
	node->parent = pNewRoot;

	if (pa == head)
	{
		head->parent = pNewRoot;
		pNewRoot->parent = head;
	}
	else
	{
		node->key > pa->key ? pa->right = pNewRoot : pa->left = pNewRoot;
		pNewRoot->parent = pa;
	}
}

template<typename T>
void AvlTree<T>::RotateRight(AvlNode<T>* node)
{
	AvlNode<T>* pa = node->parent;
	AvlNode<T>* pNewRoot = node->left;

	node->left = pNewRoot->right;
	if (pNewRoot->right != nullptr)
	{
		pNewRoot->right->parent = node;
	}

	pNewRoot->right = node;
	node->parent = pNewRoot;

	if (pa == head)
	{
		head->parent = pNewRoot;
		pNewRoot->parent = head;
	}
	else
	{
		node->key > pa->key ? pa->right = pNewRoot : pa->left = pNewRoot;
		pNewRoot->parent = pa;
	}
}

template<typename T>
void AvlTree<T>::LeftBalance(AvlNode<T>* node)
{
	AvlNode<T>* leftsub = node->left;
	AvlNode<T>* rightsub = nullptr;
	switch (leftsub->balance)
	{
	case 0:
		break;
	case -1:
		node->balance = 0;
		leftsub->balance = 0;
		RotateRight(node);
		break;
	case 1:
		rightsub = leftsub->right;
		switch (rightsub->balance)
		{
		case -1:
			node->balance = 1;
			leftsub->balance = 0;
			break;
		case 1:
			node->balance = 0;
			leftsub->balance = -1;
			break;
		case 0:
			node->balance = 0;
			leftsub->balance = 0;
		}
		rightsub->balance = 0;
		RotateLeft(leftsub);
		RotateRight(node);
		break;
	}
}

template<typename T>
void AvlTree<T>::RightBalance(AvlNode<T>* node)
{
	AvlNode<T>* rightsub = node->right;
	AvlNode<T>* leftsub = nullptr;
	switch (rightsub->balance)
	{
	case 0:
		break;
	case 1:
		rightsub->balance = 0;
		node->balance = 0;
		RotateLeft(node);
		break;
	case -1:
		leftsub = rightsub->left;
		switch (leftsub->balance)
		{
		case 1:
			node->balance = -1;
			rightsub->balance = 0;
			break;
		case -1:
			node->balance = 0;
			rightsub->balance = 1;
			break;
		case 0:
			node->balance = 0;
			rightsub->balance = 0;
		}
		leftsub->balance = 0;
		RotateRight(rightsub);
		RotateLeft(node);
		break;
	}
}

template<typename T>
void AvlTree<T>::AdjustTree(AvlNode<T>* node)
{
	AvlNode<T>* pa = node->parent;
	bool tall = true; //高度是否变化
	for (; tall && pa != head;)
	{
		if (pa->left == node)
		{
			switch (pa->balance)
			{
			case 0: pa->balance = -1; break;	
			case 1: pa->balance = 0; tall = false; break;
			case -1: LeftBalance(pa); tall = false; break;
			}
		}
		else
		{
			switch (pa->balance)
			{
			case 0: pa->balance = 1; break;
			case -1: pa->balance = 0; tall = false; break;
			case 1:  RightBalance(pa); tall = false; break;
			}
		}
		node = pa;
		pa = node->parent;
	}
}

template<typename T>
int AvlTree<T>::DepthOfBinaryTree(AvlNode<T>* root)
{
	if (root == nullptr)
		return 0;
	int DL = DepthOfBinaryTree(root->left);
	if (DL == -1) return -1;
	int DR = DepthOfBinaryTree(root->right);
	if (DR == -1) return -1;

	return abs(DL - DR)>1 ? -1 : DL>DR ? DL + 1 : DR + 1;
}